Digital image generators are used to produce sequences of video images in real time corresponding to a user's changing position and orientation in a database of digitally-described objects. Digital image generators have found widespread utility for flight simulation, military training simulation and, increasingly now, for general training and for entertainment systems.
Basic methods for producing digitally generated images from arbitrary positions and with arbitrary orientations in a three dimensional polygonal database are described by James D. Foley in Computer Graphics, Second Edition, Addison-Wesley Publishing Company, 1990. All digital image generation methods must deal with a central problem: how to determine, for each pixel in the image, which polygons in the database make a visible contribution to the pixel's color and intensity and which are occluded and made no contribution. Two general approaches to this problem involve what are called priority lists and z-sorting.
With the priority-list based approaches, at some early stage of the image generation process, an ordered list of polygons that are near or within the boundaries of the to-be-generated image is produced for use in later stages of this processing. When two polygons are projected to the same region of the screen, competing for the same pixels and subpixels, the contribution taken for a pixel or a subpixel is that of the polygon that appears earlier on this list.
Contributions to individual pixels and regions are accumulated from the polygons, in the order in which they appear on the list, until these pixels and regions are considered complete. Possible contributions to these pixels from polygons farther down the list are ignored.
Any incorrect ordering of the polygons on this priority list can produce anomalies in the displayed image. This priority list method for the determination of occlusion relationships is inherent in image generators employing the methods described in the following patents: U.S. Pat. No. 4,570,233 to Johnson Yan, et. al. on Feb. 11, 1986; and U.S. Pat. No. 4,811,245 to William Bunker, et.al. on Mar. 7, 1989.
Image generators that rely on priority lists to determine occlusion relationships require more elaborate database structures to facilitate the determination of a correct priority ordering for the potentially displayable polygons. In addition, certain geometric arrangements of the database elements do not allow a priority list ordering (for example, interpenetrating polygons), and thus, limitations are necessary on the placement of polygons within the databases of these types of image generators. These limitations become particularly troublesome when there are moving models in the generated image.
With z-sorting approaches, occlusion determination takes place near the end of the image generation process. With this type of approach, when polygons contend for a contribution to a given pixel, this contention is resolved at this pixel level by comparing the z values at this pixel of the contending polygons (the contributions of the polygons with the smallest z values are used).
Occlusion processing approaches that employ z sorting can be computationally intensive because it is necessary to compute and compare z values for every polygon at every pixel and subpixel for which there is contention. In U.S. Pat. No. 4,918,626 to Gary Watkins, et.al. on Apr. 17, 1990, a method is described that saves some of the computations; however, contention resolution is still accomplished at the pixel and subpixel level on a polygon by polygon basis.
In U.S. Pat. No. 4,594,673 to James R. Holly, et.al. on Jun. 10, 1986, a scanline oriented method is described that can accomplish the sorting of polygons along scanlines without resorting to pixel z comparisons. This method, however, does not incorporate the processing of non-opaque (translucent) polygons, but rather, it also requires many comparisons of a current polygon with previously processed polygons in most cases, even though the current polygon may clearly be occulted by or may occult all of the other polygons.
Thus, prior art methods using priority lists accomplish occlusion processing efficiently but require special database structures. They have difficulties with objects moving in the scene. Z sorting methods eliminate the constraints of database structures and have no difficulty with moving objects, but they are computationally intensive due to the large number of Z comparisons required and, as a result, tend to be expensive to implement.